/*
 * @lc app=leetcode id=152 lang=cpp
 *
 * [152] Maximum Product Subarray
 */
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int len = nums.size();
        if (len < 1) {
            return 0;
        }

        vector<int> maxdp(len);
        vector<int> mindp(len);

        maxdp[0] = nums[0];
        mindp[0] = nums[0];
        int maxRet = nums[0];

        for (int i = 1; i < len; i++) {
            if (nums[i] > 0) {
                maxdp[i] = std::max(maxdp[i-1] * nums[i], nums[i]);
                mindp[i] = std::min(mindp[i-1] * nums[i], nums[i]);
            } else {
                maxdp[i] = std::max(mindp[i-1] * nums[i], nums[i]);
                mindp[i] = std::min(maxdp[i-1] * nums[i], nums[i]);
            }
            maxRet = std::max(maxdp[i], maxRet);
        }

        return maxRet;
    }
};

